1. Field of the Invention
The present invention relates to a branch metric calculation method and a Viterbi decoder in Viterbi decoding in which a branch metric is derived by comparing a codeword produced from a convolutional code with a sign in determination data obtained from conversion of received data for branch metric calculation.
2. Description of the Related Art
Conventionally, in mobile stations in digital cellular mobile telephone systems of a TDMA scheme or a CDMA scheme and digital satellite communication of the CDMA scheme, errors arising in transmission paths are corrected with an error correcting code for obtaining desired channel quality. In the processing with the error correcting code, error bits are detected for correction. The code for the correction is broadly divided, based on methods of random error correction, into a block code or a convolutional code and a concatenated code in which the block code and convolutional code are combined.
Viterbi decoding is well known as decoding at a receiving part for the convolutional code (see Literature xe2x80x9cDigital Satellite Communication,xe2x80x9d Kazunori Tamura and Tatsuro Masamura, The Telecommunications Association). The Viterbi decoding is an algorithm which can efficiently perform maximum likelihood decoding with the convolutional code by selecting the path closest to the received sequence from two paths joining from certain states. The Viterbi decoding has a relatively high ability for correcting errors arising in transmission paths, and produces high coding gain in combination with a Soft-Decision Decoding scheme. The Viterbi decoding, however, involves large processing and circuit scales, and reductions thereof are problems to be tackled.
Branches are produced corresponding to states of respective node decoders in a tree representation which is a representation for the convolutional code. Specifically, the tree representation is a trellis representation for showing changes in states of independent coders in which two branches are produced corresponding to state 0 or state 1 for input 1 bit. From the trellis, metrics are calculated for providing certainty of paths or branches. In the branch metric calculation method, a codeword of each state produced from the convolutional code is compared with a sign in determination data, and if they match, it is determined that the associated metric is 0, or if they do not match, the metrics of the determination data are added to calculate a branch metric.
FIG. 1 is a circuit diagram showing a configuration for performing conventional branch metric calculation. In FIG. 1, description is made on the assumption that the coding rate is ⅓ and the number of states is 256.
Metric data 1, 2 and 3 are supplied to latch circuits 26a, 26b and 26c, respectively. Latch circuits 26a to 26c hold metric data 1 to 3, respectively, until latch pulses are supplied thereto. After the latching, latch circuits 26a to 26c output metric data of K bits for state N. Inverters 27a, 27b and 27c invert the metric data of K bits for N state to metric data of k bits for state N+128 before output.
The metric data of K bits for state N and the metric data of k bits for state N+128 are supplied to time-division switches 28a, 28b and 28c. Time-division switches 28a to 28c switch to select and output the metric data for state N or the metric data for state N+128, respectively, in accordance with timing pulses.
The aforementioned number of states 256 is a typical value for the number of states in the Viterbi decoding in a digital cellular mobile telephone system or the like. The number xe2x80x9c128xe2x80x9d in the metric data of k bits for state N+128 is equal to xc2xd of the number of states 256 for a butterfly structure in state transition in the Viterbi decoding, later described in FIG. 4.
The metric data for state N or the metric data for state N+128 selected by time-division switches 28a to 28c are supplied to word split circuits 29a, 29b and 29c, respectively. Word split circuits 29a to 29c divide the metric data for state N or the metric data for state N+128 into signs and metrics before output, respectively. The sign of 1 bit separated at each of word split circuits 29a to 29c is supplied to each of EX-OR (exclusive OR) gates 33a to 33c. EX-OR gates 33a to 33c also receive codewords (g0, g1 and g2) for each state obtained from processing in convolutional code generator 35, and counter (N=0 to 127) 34, and make determination about the signs with EX-OR operations.
In accordance with the outputs from EX-OR gates 33a to 33c, selectors 30a, 30b and 30c select the metrics from word split circuits 29a to 29c or 0 (Z). The selected outputs are added at adders 32a and 32b to calculate a branch metric.
The Viterbi decoding for performing such branch metric calculation involves large processing and circuit scales as compared with processing of threshold decoding in block coding (for example, with BHC code or Golay code) and in convolutional coding or the like, and reductions thereof are problems to be tackled. Thus, various proposals have been made for reducing the processing and circuit scales.
As one of the proposals, in a prior art of xe2x80x9cViterbi Decoderxe2x80x9d in Japanese Patent Laid-open Publication No.6-303153, outputs from branch metric operation means which are supplied to an ACS (Add/Compare/Select) unit are controlled in a time-division manner for reducing the circuit scale of the Viterbi decoder. For maximum likelihood determination in maximum likelihood determination means, outputs from path metric resistors are processed in a time-division manner at compare/select circuits in the ACS unit. The scale of the maximum likelihood determination means is thus reduced to reduce the processing and circuit scales of the Viterbi decoder.
In a prior art of xe2x80x9cBranch Metric Operation Circuitxe2x80x9d in Japanese Patent Laid-open Publication No.7-131494, for reducing the processing and circuit scales resulting from the reduced number of bits in a branch metric operation circuit, trellis decoding uses the square of the Euclid distance between received symbols and representative symbols of a subset, and the square of the Euclid distance is used as a branch metric as it is. Also, bits are reduced by imposing amplitude limitations on the received symbol. In addition, bits are truncated at an output of Euclid distance calculation means to reduce the processing and circuit scales.
In a prior art of xe2x80x9cViterbi Decoding Method and Apparatusxe2x80x9d in Japanese Patent Laid-open Publication No.10-200419, a path memory update operation and an output operation are simultaneously performed and respective sets of units are alternately operated with shifted phases. Thus, the scale of the path memory is reduced, and the processing and circuit scales are reduced in the Viterbi decoder.
The aforementioned prior art Viterbi decoders have the large processing and circuit scales, and reductions in the scales are problems to be overcome.
In the prior art shown in FIG. 1, the metric data of K bits for state N or the inverted metric data of k bits for state N+128 after the latching is selected by time-division switches 28a to 28c for k bits in accordance with the timing pulses. Therefore, when multiplexers are used, for example, as time-division switches 28a to 28c for k bits, the configuration for switching k bits is complicated to increase the processing and circuit scales.
For this reason, it is difficult to reduce the processing and circuit scales in control offices and mobil stations in cellular mobile telephone systems of a TDMA scheme, a TDMA/TDD scheme or a CDMA scheme, or satellite stations and ground stations in digital satellite communication, and especially in cellular phones, the prior art has a disadvantage of difficulties in meeting demands for size reduction and multiple functions.
In addition, while the prior arts in the gazettes described above can reduce the processing and circuit scales in the Viterbi decoding, they are susceptible to improvement in terms of simplification of the operation methods.
It is an object of the present invention to provide a branch metric calculation method and a Viterbi decoder which solve the aforementioned problems in the prior arts and reduce the number of bits in branch metric calculation processing to diminish the processing scale and the circuit scale, and for example, reduce the processing scale and the circuit scale in devices in digital cellular mobile telephone systems of TDMA, TDMA/TDD schemes or a CDMA scheme.
To achieve the aforementioned object, the branch metric calculation method in Viterbi decoding of the present invention derives a branch metric by comparing a codeword produced from a convolutional code with a sign in determination data obtained from conversion of received data for branch metric calculation. First, the determination data is divided into a sign and a metric before output. Then, a check is made to determine whether or not the divided sign matches the codeword. Next, based on the result of the match or mismatch, xe2x80x9c0xe2x80x9d is selected when they match or the metric is selected when they do not match. Outputs selected when the signs match are added to outputs selected when the signs do not match to calculate a branch metric.
The Viterbi decoder of the present invention derives a branch metric by comparing a codeword produced from a convolutional code with a sign in determination data obtained from conversion of received data for branch metric calculation. The Viterbi decoder comprises a metric data convertor, a code generator, a branch metric calculator, an add/compare/select operator, a path metric memory, a path information memory, and a trace back processor.
The metric data convertor outputs a plurality of metric data obtained by converting a received data sequence to soft decision symbols. The code generator generates and outputs codewords.
The branch metric calculator divides the plurality of metric data from the metric data convertor into signs and metrics, respectively, outputs them, and determines whether the divided signs match the codewords from the code generator. The branch metric calculator selects and outputs xe2x80x9c0xe2x80x9d when they match or selects and outputs the metrics when they do not match based on the determination result of the match or mismatch, and adds outputs selected when the signs match to outputs selected when the signs do not match to calculate a branch metric.
The add/compare/select operator adds the branch metric calculated by the branch metric calculator to a path metric of a survivor path, and makes a comparison and a selection of the metrics of two joining paths to calculate a new path metric and a survivor path. The path metric memory stores the new path metric and the survivor path metric from the add/compare/select operator, and sends a survivor path metric to the add/compare/select operator.
The path information memory holds survivor paths for a plurality of states from the add/compare/select operator. The trace back processor decodes the state with the smallest path metric at final truncation of bits from the path metric memory and survivor paths for the plurality of states from the path information memory.
According to an embodiment of the present invention, the branch metric calculator includes a plurality of division means, a plurality of determination means, a plurality of time-division selection means, and adding means.
The plurality of division means divide the plurality of input metric data into signs and metrics, respectively, and output them. The plurality of determination means determine whether or not the respective signs divided by the plurality of division means match the codewords input thereto. The plurality of time-division selection means select outputs obtained by not inverting or inverting the results of the match or mismatch determined by the plurality of determination means. The addition means add outputs selected when the signs match to the metrics divided and output by the plurality of division means selected when the signs do not match in the selection of the plurality of time-division selection means to calculate a branch metric.
According to another embodiment of the present invention, the plurality of division means are word split circuits, respectively, and each of the word split circuits divides each of the plurality of input metric data into a sign and a metric and outputs them.
According to another embodiment of the present invention, the plurality of determination means are exclusive OR gates, respectively, and each of the exclusive OR gates determines whether or not each of the signs divided by the plurality of division means matches each of the codewords input to each of the exclusive OR gates.
According to a further embodiment of the present invention, the addition means includes two adders for adding outputs when the signs match to outputs when the signs do not match based on the selection at the plurality of time-division selection means to calculate a branch metric.
In addition, according to another embodiment of the present invention, the inversion of the output result of the match or mismatch determined by each of the plurality of determination means is performed using an inverter.
According to another embodiment of the present invention, the Viterbi decoder further comprises a plurality of latch circuits on the sides of respective inputs to the plurality of word split circuits for holding the input metric data until latch pulses are input.
According to another embodiment of the present invention, each of the word split circuits divides each of the plurality of input metric data into the most significant bit for sign determination and a metric of kxe2x88x921 bits.
According to another embodiment of the present invention, each of the signs and the codewords input to each of the plurality of exclusive OR gates comprises one bit.
According to another embodiment of the present invention, each of the plurality of time-division selection means is a multiplexer.
In such a branch metric calculation method and such a Viterbi decoder in Viterbi decoding of the present invention, each of the plurality of metric data is divided into the sign of the least 1 bit and the metric of kxe2x88x921 bits in the branch metric calculation. A check is made to determine whether or not the divided signs (the least 1 bit) match the codewords (the least 1 bit) for each state produced from the convolutional code, and the outputs of the match or mismatch are selected by the time-division selection means for 1 bit, for example multiplexers. The outputs selected when the signs match are added to the divided and output metrics selected when the signs do not match to calculate a branch metric.
The conventional branch metric calculation shown in FIG. 1, for example, uses time-division selection means (time-division switches) for k bits for state N+128 with large processing and circuit scales.
In the branch metric calculation processing of the present invention, however, each of the plurality of time-division selection means (multiplexers) may be configured to select 1 bit from the symmetry of a butterfly structure in Viterbi decoding. In other words, the number of bits is reduced and the processing is simplified to allow the processing scale and the circuit scale to be reduced.
The above and other objects, features and advantages of the present invention will become apparent from the following description with reference to the accompanying drawings which illustrate examples of the present invention.